Cuối tháng 5 năm 1081, 150 tàu của hạm đội Norman, trong đó bao gồm 60 tàu chở ngựa chiến, đã tiến vào vùng biển của Đế quốc Đông La Mã. Có 30.000 quân được tập hợp và tham gia cuộc viễn chinh, cùng với sự hỗ trợ của 1300 hiệp sĩ Norman.[16] Khi tiến tới Avalona thuộc lãnh thổ Đông La Mã, một số tàu từ Ragusa, một nước cộng hòa ở Balkan từ lâu đã đối địch với Đông La Mã, đã gia nhập hạm đội của họ.[17]

Robert sớm rời khỏi Avalona và đi thuyền tới đảo Corfu, nơi mà các đơn vị đồn trú ít ỏi dường như đã đầu hàng ngay lập tức. Chiếm được một cầu nối với Hy Lạp đồng thời là một căn cứu để nhận tiếp tế từ Ý, Robert hướng đến Dyrrhachium, cảng chính và thủ phủ của Illyria.[18] Thành phố này được bảo vệ bằng một dải đất dài, tạo thành một bán đảo hẹp chạy song song với bờ biển, nhưng bị ngăn cách bởi đầm lầy. Robert Guiscard đổ quân lên bán đảo rồi dựng doanh trại bên ngoài hàng phòng thủ của thành phố.[19] Tuy nhiên, khi hạm đội của ông ta tiến tới Dyrrhachium đã gặp phải một cơn bão, làm đắm mất một số tàu.[17]

Khi nhận được tin người Norman chuẩn bị xâm lược đế quốc, Alexios đã nhanh chóng gửi một đại sứ tới chỗ Domenico Selvo, tổng đốc của Venice, đề nghị dành cho họ những đặc quyền về thương mại đổi lấy sự hỗ trợ về quân sự.[17] Tổng đốc Venice vốn đang lo ngại trước việc người Norman có thể kiểm soát eo biển Otranto, liền đích thân chỉ huy hạm đội và giương buồm ra khơi ngay sau đó. Hạm đội Venice tấn công bất ngờ vào các tàu Norman ngay trong đêm. Dưới sự chỉ huy của Bohemond, quân Norman kháng cự kịch liệt nhưng kinh nghiệm đi biển ít ỏi đã chống lại họ. Hạm đội Venice dày dặn kinh nghiệm đã dàn theo thế trận "cảng biển" đánh thẳng vào các tàu chiến Norman, được sự trợ giúp của Lửa Hy Lạp và đạn lửa từ các tàu Đông La Mã bên trong cảng, họ đánh tan tác hạm đội Norman và tiến vào trong cảng Dyrrhachium.[20]